/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */

// 没有体现是二叉搜索树
/**
 * Encodes a tree to a single string.
 *  先序遍历
 * @param {TreeNode} root
 * @return {string}
 */
var serialize = function (root) {
  if (!root) {
    return '';
  }
  const children = root.left || root.right ? `(${serialize(root.left)},${serialize(root.right)})` : '';
  return `${root.val}${children}`;
};

/**
 * Decodes your encoded data to tree.
 *
 * @param {string} data
 * @return {TreeNode}
 */
var deserialize = function (data) {
  let i = 0,
    scode = 0,
    str = '',
    root = null,
    // 当前节点
    p,
    side,
    list = [];
  while (i < data.length) {
    switch (scode) {
      case 0:
        if (data[i] >= '0' && data[i] <= '9') {
          scode = 1;
        } else if (data[i] === '(') {
          scode = 2;
        } else if (data[i] === ',') {
          scode = 3;
        } else if (data[i] === ')') {
          scode = 4;
        }
        break;
      // 处理节点
      case 1:
        scode = 0;
        while (data[i] >= '0' && data[i] <= '9') {
          str += data[i];
          i++;
        }
        p = new TreeNode(parseInt(str));
        // 清空str
        str = '';
        if (!root) {
          root = p;
        } else if (side === 0) {
          list[list.length - 1].left = p;
        } else if (side === 1) {
          list[list.length - 1].right = p;
        }
        break;
      case 2:
        scode = 0;
        side = 0;
        list.push(p);
        i++;
        break;
      case 3:
        scode = 0;
        side = 1;
        i++;
        break;
      case 4:
        scode = 0;
        i++;
        list.pop();
        break;
    }
  }
  return root;
};

/**
 * Your functions will be called as such:
 * deserialize(serialize(root));
 */
